package stack;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 用栈实现队列
 */
public class ImplementQueueUsingStacks {
  public static void main(String[] args) {
    MyQueue queue = new MyQueue();
    queue.push(1);
    queue.push(2);
    System.out.println(queue.peek());
    System.out.println(queue.pop());
  }

  static class MyQueue {

    Deque<Integer> inputStack;
    Deque<Integer> outputStack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
      inputStack = new LinkedList<>();
      outputStack = new LinkedList<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
      inputStack.addFirst(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
      if (!outputStack.isEmpty()) {
        return outputStack.removeFirst();
      }
      while (!inputStack.isEmpty()) {
        outputStack.addFirst(inputStack.removeFirst());
      }
      if (!outputStack.isEmpty()) {
        return outputStack.removeFirst();
      } else {
        return -1;
      }
    }

    /**
     * Get the front element.
     */
    public int peek() {
      if (!outputStack.isEmpty()) {
        return outputStack.getFirst();
      }
      while (!inputStack.isEmpty()) {
        outputStack.addFirst(inputStack.removeFirst());
      }
      if (!outputStack.isEmpty()) {
        return outputStack.getFirst();
      } else {
        return -1;
      }
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
      return (inputStack.isEmpty() && outputStack.isEmpty()) ? true : false;
    }
  }

}
